Manipulation resistant records that can be relied upon and updated efficiently are important for the efficient functioning of organizations ranging from governments, to companies, to various associations. Records such as votes or financial transactions require a high level of manipulation resistance. Many record keeping systems fail to sufficiently protect against manipulation. Alternatively, the required level of manipulation resistance results in cumbersome and expensive systems of checks, balances, and audits.
Critical record keeping, and in particular the exchange of value, is increasingly moving into the digital realm. Everything from game points, credits, frequent flyer miles, to more traditional financial transactions and records are being tracked digitally. Most of these digital records are tracked by a central record keeping entity or issuing authority. Keeping track of transferrable ownership rights historically required a central record keeping authority trusted by those exchanging said ownership rights. The record keeping authority typically verifies property owners via some form of identification or signature and records all valid property transfers to maintain a record of the current state of ownership. Banks using digital representations of money are trusted to verify identities and keep accurate records of deposits and transfers. Governments keep records of property titles and transfers. A company issuing reward points or game points would also fulfill this role.
There are times, however, when relying on a central authority is not desirable. Participants who rely on digital records to be recorded accurately may feel that a central authority is a single point of potential failure and a single point of trust. This authority may be subject to various internal or external pressures or corruption. There is a need and market for systems of record keeping that function in a more decentralized fashion, thus spreading power over checks, balances, and audits to many participants and automating these processes. For example, crypto-currencies (also referred to herein as cryptocurrency), such as Bitcoin promoted by Bitcoin.org (“Bitcoin”), track digital tokens in a more decentralized manner. A digital currency can be viewed as a prototypical digital ledger that records the association of balances with particular owners. Digital currency units may alternatively be referred to herein as balances or digital assets, tokens, or stake.
Achieving consensus on a digital ledger of transferable ownership rights without a central record keeping authority however presents a considerable technical challenge. The challenge can be broken into a two part problem of achieving verifiable signatures for transfers and maintaining a ledger that is consistent among all participants.
The application of public key cryptography solves one part of the challenge of a peer-to-peer digital currency. Crypto-currencies use cryptographic digital signatures in place of traditional methods of identity verification as proof of ownership of digital assets. Public key cryptography signing algorithms allow for unambiguous digital signatures. A private cryptographic key is a large random number generated locally on a user's computer such that it is known only to that user. A public key can be derived from the private key. As long as the private key is kept secret, any signature produced using the private key serves as proof that the signer is the same party that originally published the public key. In addition to proving the source of a signed message, the signature also ensures that no data in the message can be lost or changed without invalidating the signature. Public keys can be recorded in a ledger of ownership rights. Digital assets can be associated with these public keys such that the public keys serve as the digital representation of the owner of the assets. A transfer of ownership of a digital asset from one public key to another can be signed with the secret private key of the sender to prove the authenticity and integrity of the message.
Unambiguous digital signatures, while useful, do not fully solve the problem of verifiable trusted record keeping. If we imagine an initial public ledger with an agreed upon list of public keys and associated digital assets, any transfers would need to be signed with the corresponding private key known only to the sender in order to be accepted. Any central record keeping authority tasked with recording changes and transfers to the ledger would have no way to forge such a transfer if it was not initiated and signed by the sender. However, many potential combinations of a set (meaning one or more) of valid signed transactions could be joined together by a record keeper to create a seemingly valid record. For instance, some transfers could simply be omitted or censored.
It is also possible for two transactions to each be individually valid but conflict with each other, thus giving the record keeper the choice of which to present. For instance, a digital asset owner may attempt to sell the same asset twice by signing two or more messages that each transfers the asset to a different public key. In such a case, the owner is said to be double spending her asset and the issue of double spending is referred to herein as a Double Spend problem. An untrustworthy record keeper could choose to present different versions of the record at different times or to different people such that the record, even with valid signatures, could not be relied upon.
Accordingly, a decentralized (also referred to herein as peer-to-peer) digital record system that achieves agreement on the record while overcoming additional systemic challenges is desired. Such a system is referred to herein as a consensus system. As used herein, consensus refers to the process by which the entire network agrees on the same ledger. Accordingly, a consensus system is a networked system capable of reaching consensus. Network latency associated with global data transmission prevents all peers from receiving information at the same time or in the same order. Peers may disconnect and reconnect at will, data can be corrupted or missing, and some peers may intentionally supply or relay inaccurate information. These types of challenges to consensus are a long recognized problem in computer science known as a Byzantine Generals Problem. The consensus system must overcome such challenges to allow the creation of a record that can be trusted and cannot be easily manipulated.
Bitcoin is the most well-known attempt to tackle the problem of peer-to-peer consensus for digital token tracking. Peers on a global network will not receive all broadcasted transactions at the same time and in the same order due to, for example, network latency. Therefore, if peers were to simply accept all transactions as they were received and reject anything conflicting that came later, it would lead to disagreement. For instance, if two conflicting transactions were simultaneously broadcast, some peers would receive one transaction first and accept it, and other peers would receive the other transaction first and accept it instead, so there would no longer be a consistent record. In this case, some peers would need to switch to maintain consistency. On the other hand, it should not be possible to get the network to switch to a conflicting transaction broadcast long after the original, as this would defeat the utility of the trustable ledger system.
Bitcoin tackles this issue by grouping transactions into blocks which can generally be propagated to the whole network before a new block of transactions is produced. For example, approximately six times per hour, a new group of accepted transactions, a block, is created, added to a block chain, and quickly published to all nodes on the transaction network system. The rate of this block production is limited by requiring inclusion of a difficult to find solution to a cryptographic function based on the previous block and current block data. If valid solutions are found too quickly, the size of the range of valid solutions adjusts to be more restrictive to increase the difficulty and maintain a reasonably steady rate of block production. Each block references and builds off a previous block using cryptographic functions called hashes. A hash function takes arbitrary digital data as input and returns a fixed length pseudo random number as output. To solve a block, an additional piece of data must be found that when combined with block data, and data that links to the previous block, generates a hash function output that falls within a very restrictive range set by the protocol. Tying each block to its previous block with these hash functions generates what is known as a block chain containing all accepted transactions. A block chain thus forms a public record of all transactions. A current ledger representing the state of ownership of digital tokens can be deduced from the full record of transactions in a block chain beginning with the first block. In a block chain, each block contains a cryptographic hash of the immediate previous block or a similar reference that links it to the immediate previous block. If any data is changed or missing, the calculated cryptographic hashes would change for all blocks from that point forward. The changed hashes would also no longer fall within the restrictive range required by the Bitcoin protocol, so the chain would be invalid.
In the Bitcoin protocol, a valid solution to a block is called a proof of work (“PoW”) and the process of finding these solutions is called mining. In other words, mining is the activity of verifying and recording payments into the public ledger. The miner of a block accepted by the network is rewarded in the form of Bitcoin transaction fees from included transactions in addition to a fixed block reward. Only the longest block chain that includes the most PoW is accepted by the network as the consensus block chain. If more than one block solution is found at the same time only one of these blocks can ultimately be accepted, as each block in the chain must reference the preceding block. Other miners must choose to work on a solution that builds off one of these two available blocks and the next published block will make one block chain longer than the other. The shorter chain is then rejected by the network and its miner cannot redeem the block reward.
Miners try to make sure they are always working on the longest known chain in order to ensure that any block found is accepted in the longest chain (also referred to herein as LC) to get the reward. Miners will quickly abandon any shorter chains to avoid expending work without reward. This creates a cooperative process where self-interested miners must cooperate to extend a single longest chain. The longer the chain becomes that builds on an included transaction the more difficult it is to change that transaction. Changing the transaction would require building a longer chain with more proof of work than the public chain. Considering the public chain is built via a cooperative process of miners all over the world, building a longer chain is not an easy task. To create a longer chain in secret in order to change a transaction (such as Double Spend) would essentially require controlling more computation power than the rest of the network combined. It is assumed to be unlikely that any party will control more computation power than the rest of the network adding to the public chain.
Bitcoin's PoW consensus algorithm (also referred to herein as protocol) however, has drawbacks. As the value of Bitcoin has grown, Bitcoin mining has become very competitive. Rather than a decentralized network of people performing PoW using their personal computers, huge warehouses with specialized hardware have been set up to maximize efficiency. Mining pools have been created so operators can pool their PoW together to share block rewards and reduce the uncertainty of reward payouts. PoW also relies on arbitrarily difficult computation and the difficulty is automatically increased if solutions are found too quickly. This computation for the sake of proving computation consumes an enormous amount of electricity. Economies of scale in PoW mining have also allowed control over the Bitcoin ledger to be more centralized than originally anticipated. Therefore, there is a high demand for more efficient algorithms to achieve consensus on a signed shared ledger over a decentralized computer network.
Many attempts have been made to find better PoW algorithms that are more conducive to being solved using standard consumer computing equipment and more resistant to the creation of cheap specialized mining hardware. The Litecoin™ project (Litecoin.org) is an example of such an attempt. These attempts have only delayed the creation of specialized mining hardware and still suffer the same centralization problems due to economies of scale. Specialized hardware is now available for mining Litecoin™. The solution of using a different PoW algorithm also does not address issues of energy waste.
A number of other strategies to consensus have been proposed or are being developed. These consensus algorithms are often implemented in popular crypto-currencies. Crypto-currencies that employ the recently proposed consensus algorithms include Ripple™ (proposed by Ripple Labs), Peercoin (also known as PPCoin or PPC), NXT (an open source cryptocurrency and payment network launched in November 2013 by anonymous software developer BCNext), and BitShares (a decentralized exchange network system proposed by Bitshares.org).
The Ripple™ network uses a consensus algorithm that does not rely on PoW. Ripple™ protocol relies on participants to select a list of trusted nodes and considers transactions confirmed when sufficient agreement is reached among those nodes. A drawback to the Ripple™ consensus algorithm is that there is no system to determine an unambiguous set of validating nodes. If different participants choose to trust different nodes consensus may not be achieved. The means by which a generally accepted list of validating nodes is created may be centralized and choosing alternate nodes creates a risk to the participant of not being in consensus with other participants.
A shared concept behind a number of recently proposed consensus protocols is called proof of stake (“PoS”) as opposed to PoW. With PoW, the ability to extend the transaction ledger is proportional to computing power. The idea behind PoS is to make control of the public ledger proportional to ownership stake of the digital currency. It is hoped that PoS will be more energy efficient and more appropriately distribute control over the ledger. A number of PoS systems are structured in a similar way to PoW mining. Just as in PoW mining, PoS mining (also called staking, minting, or forging) requires finding blocks whose block hash falls within a restrictive range; the inclusion of a block in the consensus chain entitles the PoS miner to a block reward. However, the difficulty of finding a valid block hash or the range of valid solutions depends on the ownership stake controlled by the miner who signs the block. Both Peercoin and NXT utilize such a system where stakeholders use their stake to mine for blocks.
There are numerous drawbacks to this method of consensus as well. Unlike with PoW mining, PoS miners do not incur substantial calculation costs when looking for valid block solutions that are not on the current longest chain. Therefore, creating a longer chain than the current longest public chain might be more likely as there is less cost to look for it. Drawbacks to proof of stake systems such as this are known as “Nothing at Stake” problems wherein there isn't sufficient cost, risk, or difficulty to creating an alternate blockchain that could conflict or supplant the public consensus blockchain.
Another example of a nothing at stake problem is the use of old private keys that no longer control balances on the public blockchain to build an alternate blockchain. This problem is sometimes referred to as long range nothing at stake. Many POS systems integrate regular checkpoints that offer some protection against this. A checkpoint prevents a node's software from considering any alternate blockchain that does not contain the checkpoint block. These checkpoints might be distributed by a particular entity such as a software developer or the software itself may create regular checkpoints when it is connected to the network. The downside to relying too much on checkpoints is that it creates the possibility for the network to not form a consensus on one blockchain. If one node accepts a checkpoint that isn't used by all other nodes, a blockchain could emerge that is accepted by some nodes and rejected by others.
Not every stakeholder of a POS blockchain system may desire to maintain a connected node on a personally controlled computer at all times. Such stakeholders are unable to directly participate in validating transactions on the network in real time. Some POS systems allow for stakeholders to delegate this power to validate the block chain to others. This has typically taken the form of “stake leasing” where a balance can be delegated to a single other public key for the purpose of block signing. Stake leasing is implemented on the N×T block chain. Stake leasing was also part of the original design of Delegated Proof of Stake (DPOS) as proposed for the BitShares block chain in April, 2014. A drawback to stake leasing is a potential misalignment of incentives that creates centralization due to leasing to the highest bidder. The means by which delegation occurs and the incentives provided for it must be carefully considered or this will inappropriately concentrate power over the block chain.
Decentralized systems for updateable digital records must reach consensus in the face of network latency, data corruption, and various intentional methods to manipulate or disrupt the system. Accordingly, there is a need for a new peer-to-peer consensus system that provides verifiable signatures and maintains a ledger that is consistent among all participants of the networked system. The new system achieves consensus with less power consumption. In addition, the new system achieves consensus despite network latency, data corruption and other issues. In addition the new system maintains a ledger that is resistant to Double Spend or other intentional manipulation. In addition the new system maintains a ledger wherein superfluous signatures are removed, thus reducing the size of the ledger and improving efficiency. Furthermore, the new peer-to-peer consensus system overcomes the drawbacks of long range nothing at stake.